In the basic communication scenario, depicted in Figure 1.1, there are two parties, we’ll call them Alice and Bob, who want to communicate with each other. A third party, Eve, is a potential eavesdropper.

Figure 1.1 The Basic Communication Scenario for Cryptography.

When Alice wants to send a message, called the plaintext, to Bob, she encrypts it using a method prearranged with Bob. Usually, the encryption method is assumed to be known to Eve; what keeps the message secret is a key. When Bob receives the encrypted message, called the ciphertext, he changes it back to the plaintext using a decryption key.

Eve could have one of the following goals:

1. Read the message.

2. Find the key and thus read all messages encrypted with that key.

3. Corrupt Alice’s message into another message in such a way that Bob will think Alice sent the altered message.

4. Masquerade as Alice, and thus communicate with Bob even though Bob believes he is communicating with Alice.

Which case we’re in depends on how evil Eve is. Cases (3) and (4) relate to issues of integrity and authentication, respectively. We’ll discuss these shortly. A more active and malicious adversary, corresponding to cases (3) and (4), is sometimes called Mallory in the literature. More passive observers (as in cases (1) and (2)) are sometimes named Oscar. We’ll generally use only Eve, and assume she is as bad as the situation allows.

Cryptography is not only about encrypting and decrypting messages, it is also about solving real-world problems that require information security. There are four main objectives that arise:

1. Confidentiality: Eve should not be able to read Alice’s message to Bob. The main tools are encryption and decryption algorithms.

2. Data integrity: Bob wants to be sure that Alice’s message has not been altered. For example, transmission errors might occur. Also, an adversary might intercept the transmission and alter it before it reaches the intended recipient. Many cryptographic primitives, such as hash functions, provide methods to detect data manipulation by malicious or accidental adversaries.

3. Authentication: Bob wants to be sure that only Alice could have sent the message he received. Under this heading, we also include identification schemes and password protocols (in which case, Bob is the computer). There are actually two types of authentication that arise in cryptography: entity authentication and data-origin authentication. Often the term identification is used to specify entity authentication, which is concerned with proving the identity of the parties involved in a communication. Data-origin authentication focuses on tying the information about the origin of the data, such as the creator and time of creation, with the data.

4. Non-repudiation: Alice cannot claim she did not send the message. Non-repudiation is particularly important in electronic commerce applications, where it is important that a consumer cannot deny the authorization of a purchase.

Authentication and non-repudiation are closely related concepts, but there is a difference. In a symmetric key cryptosystem, Bob can be sure that a message comes from Alice (or someone who knows Alice’s key) since no one else could have encrypted the message that Bob decrypts successfully. Therefore, authentication is automatic. However, he cannot prove to anyone else that Alice sent the message, since he could have sent the message himself. Therefore, non-repudiation is essentially impossible. In a public key cryptosystem, both authentication and non-repudiation can be achieved (see Chapters 9, 13, and 15).

Much of this book will present specific cryptographic applications, both in the text and as exercises. Here is an overview.

One of the earliest cryptosystems is often attributed to Julius Caesar. Suppose he wanted to send a plaintext such as

but he didn’t want Brutus to read it. He shifted each letter backwards by three places, so $d$ became $A\text{,}e$ became $B\text{,}f$ became $C\text{,}$ etc. The beginning of the alphabet wrapped around to the end, so $a$ became $X\text{,}b$ became $Y\text{,}$ and $c$ became $Z\text{.}$ The ciphertext was then

Decryption was accomplished by shifting FORWARD by three spaces (and trying to figure out how to put the spaces back in).

We now give the general situation. If you are not familiar with modular arithmetic, read the first few pages of Chapter 3 before continuing.

Label the letters as integers from 0 to 25. The key is an integer $\kappa$ with $0\le \kappa \le 25$. The encryption process is

Decryption is $x\mapsto x-\kappa (\text{mod}26)$. For example, Caesar used $\kappa =23\equiv -3$.

Let’s see how the four types of attack work.

1. Ciphertext only: Eve has only the ciphertext. Her best strategy is an exhaustive search, since there are only 26 possible keys. See Example 1 in the Computer Appendices. If the message is longer than a few letters (we will make this more precise later when we discuss entropy), it is unlikely that there is more than one meaningful message that could be the plaintext. If you don’t believe this, try to find some words of four or more letters that are shifts of each other. Three such words are given in Exercises 1 and 2. Another possible attack, if the message is sufficiently long, is to do a frequency count for the various letters. The letter $e$ occurs most frequently in most English texts. Suppose the letter $L$ appears most frequently in the ciphertext. Since $e=4$ and $L=11$, a reasonable guess is that $\kappa =11-4=7$. However, for shift ciphers this method takes much longer than an exhaustive search, plus it requires many more letters in the message in order for it to work (anything short, such as this, might not contain a common symbol, thus changing statistical counts).

2. Known plaintext: If you know just one letter of the plaintext along with the corresponding letter of ciphertext, you can deduce the key. For example, if you know $t(=19)$ encrypts to $D(=3)$, then the key is $\kappa \equiv 3-19\equiv -16\equiv 10(\text{mod}26)$.

3. Chosen plaintext: Choose the letter $a$ as the plaintext. The ciphertext gives the key. For example, if the ciphertext is $H$, then the key is 7.

4. Chosen ciphertext: Choose the letter $A$ as ciphertext. The plaintext is the negative of the key. For example, if the plaintext is $h$, the key is $-7\equiv 19(\text{mod}26)$.

The shift ciphers may be generalized and slightly strengthened as follows. Choose two integers $\alpha$ and $\beta$, with $\text{gcd}(\alpha \text{,}26)=1$, and consider the function (called an affine function)

For example, let $\alpha =9$ and $\beta =2$, so we are working with $9x+2$. Take a plaintext letter such as $h(=7)$. It is encrypted to $9\cdot 7+2\equiv 65\equiv 13(\text{mod}26)$, which is the letter $N$. Using the same function, we obtain

How do we decrypt? If we were working with rational numbers rather than mod 26, we would start with $y=9x+2$ and solve: $x={\displaystyle \frac{1}{9}}(y-2)$. But ${\displaystyle \frac{1}{9}}$ needs to be reinterpreted when we work mod 26. Since $\text{gcd}(9\text{,}26)=1$, there is a multiplicative inverse for $9(\text{mod}26)$ (if this last sentence doesn’t make sense to you, read Section 3.3 now). In fact, $9\cdot 3\equiv 1(\text{mod}26)$, so 3 is the desired inverse and can be used in place of ${\displaystyle \frac{1}{9}}$. We therefore have

Let’s try this. The letter $V(=21)$ is mapped to $3\cdot 21+20\equiv 83\equiv 5(\text{mod}26)$, which is the letter $f$. Similarly, we see that the ciphertext $CVVWPM$ is decrypted back to affine. For more examples, see Examples 2 and 3 in the Computer Appendices.

Suppose we try to use the function $13x+4$ as our encryption function. We obtain

If we alter the input, we obtain

Clearly this function leads to errors. It is impossible to decrypt, since several plaintexts yield the same ciphertext. In particular, we note that encryption must be one-to-one, and this fails in the present case.

What goes wrong in this example? If we solve $y=13x+4$, we obtain $x={\displaystyle \frac{1}{13}}(y-4)$. But ${\displaystyle \frac{1}{13}}$ does not exist mod 26 since $\text{gcd}(13\text{,}26)=13\ne 1$. More generally, it can be shown that $\alpha x+\beta$ is a one-to-one function mod 26 if and only if $\text{gcd}(\alpha \text{,}26)=1$. In this case, decryption uses $x\equiv {\alpha }^{\ast }y-{\alpha }^{\ast }\beta (\text{mod}26)$, where $\alpha {\alpha }^{\ast }\equiv 1(\text{mod}26)$. So decryption is also accomplished by an affine function.

The key for this encryption method is the pair $(\alpha \text{,}\beta )$. There are 12 possible choices for $\alpha$ with $\text{gcd}(\alpha \text{,}26)=1$ and there are 26 choices for $\beta$ (since we are working mod 26, we only need to consider $\alpha$ and $\beta$ between 0 and 25). Therefore, there are $12\cdot 26=312$ choices for the key.

Let’s look at the possible attacks.

1. Ciphertext only: An exhaustive search through all 312 keys would take longer than the corresponding search in the case of the shift cipher; however, it would be very easy to do on a computer. When all possibilities for the key are tried, a fairly short ciphertext, say around 20 characters, will probably correspond to only one meaningful plaintext, thus allowing the determination of the key. It would also be possible to use frequency counts, though this would require much longer texts.

2. Known plaintext: With a little luck, knowing two letters of the plaintext and the corresponding letters of the ciphertext suffices to find the key. In any case, the number of possibilities for the key is greatly reduced and a few more letters should yield the key.

   For example, suppose the plaintext starts with if and the corresponding ciphertext is $PQ$. In numbers, this means that 8 $(=i)$ maps to 15 $(=P)$ and 5 maps to 16. Therefore, we have the equations

   $$8\alpha +\beta \equiv 15\text{and}5\alpha +\beta \equiv 16(\text{mod}26)\text{.}$$

   Subtracting yields $3\alpha \equiv -1\equiv 25(\text{mod}26)$, which has the unique solution $\alpha =17$. Using the first equation, we find $8\cdot 17+\beta \equiv 15(\text{mod}26)$, which yields $\beta =9$.

   Suppose instead that the plaintext go corresponds to the ciphertext $TH$. We obtain the equations

   $$6\alpha +\beta \equiv 19\text{and}14\alpha +\beta \equiv 7(\text{mod}26)\text{.}$$

   Subtracting yields $-8\alpha \equiv 12(\text{mod}26)$. Since $\text{gcd}(-8\text{,}26)=2$, this has two solutions: $\alpha =5\text{,}18$. The corresponding values of $\beta$ are both 15 (this is not a coincidence; it will always happen this way when the coefficients of $\alpha$ in the equations are even). So we have two candidates for the key: $(5\text{,}15)$ and $(18\text{,}15)$. However, $\text{gcd}(18\text{,}26)\ne 1$ so the second is ruled out. Therefore, the key is $(5\text{,}15)$.

   The preceding procedure works unless the gcd we get is 13 (or 26). In this case, use another letter of the message, if available.

   If we know only one letter of plaintext, we still get a relation between $\alpha$ and $\beta$. For example, if we only know that $g$ in plaintext corresponds to $T$ in ciphertext, then we have $6\alpha +\beta \equiv 19(\text{mod}26)$. There are 12 possibilities for $\alpha$ and each gives one corresponding $\beta$. Therefore, an exhaustive search through the 12 keys should yield the correct key.

3. Chosen plaintext: Choose $ab$ as the plaintext. The first character of the ciphertext will be $\alpha \cdot 0+\beta =\beta$, and the second will be $\alpha +\beta$. Therefore, we can find the key.

4. Chosen ciphertext: Choose $AB$ as the ciphertext. This yields the decryption function of the form $x={\alpha }_{1}y+{\beta }_1$. We could solve for $y$ and obtain the encryption key. But why bother? We have the decryption function, which is what we want.

A variation of the shift cipher was invented back in the sixteenth century. It is often attributed to Vigenère, though Vigenère’s encryption methods were more sophisticated. Well into the twentieth century, this cryptosystem was thought by many to be secure, though Babbage and Kasiski had shown how to attack it during the nineteenth century. In the 1920s, Friedman developed additional methods for breaking this and related ciphers.

The key for the encryption is a vector, chosen as follows. First choose a key length, for example, 6. Then choose a vector of this size whose entries are integers from 0 to 25, for example $k=(21\text{,}4\text{,}2\text{,}19\text{,}14\text{,}17)$. Often the key corresponds to a word that is easily remembered. In our case, the word is vector. The security of the system depends on the fact that neither the keyword nor its length is known.

To encrypt the message using the $k$ in our example, we take first the letter of the plaintext and shift by 21. Then shift the second letter by 4, the third by 2, and so on. Once we get to the end of the key, we start back at its first entry, so the seventh letter is shifted by 21, the eighth letter by 4, etc. Here is a diagram of the encryption process.

A known plaintext attack will succeed if enough characters are known since the key is simply obtained by subtracting the plaintext from the ciphertext mod 26. A chosen plaintext attack using the plaintext $aaaaa\dots$ will yield the key immediately, while a chosen ciphertext attack with $AAAAA\dots$ yields the negative of the key. But suppose you have only the ciphertext. It was long thought that the method was secure against a ciphertext-only attack. However, it is easy to find the key in this case, too.

The cryptanalysis uses the fact that in most English texts the frequencies of letters are not equal. For example, $e$ occurs much more frequently than $x$. These frequencies have been tabulated in [Beker-Piper] and are provided in Table 2.1.

Table 2.1 Frequencies of Letters in English

Of course, variations can occur, though usually it takes a certain amount of effort to produce them. There is a book Gadsby by Ernest Vincent Wright that does not contain the letter $e$. Even more impressive is the book La Disparition by George Perec, written in French, which also does not have a single $e$ (not only are there the usual problems with verbs, etc., but almost all feminine nouns and adjectives must be avoided). There is an English translation by Gilbert Adair, A Void, which also does not contain $e$. But generally we can assume that the above gives a rough estimate of what usually happens, as long as we have several hundred characters of text.

If we had a simple shift cipher, then the letter $e$, for example, would always appear as a certain ciphertext letter, which would then have the same frequency as that of $e$ in the original text. Therefore, a frequency analysis would probably reveal the key. However, in the preceding example of a Vigenère cipher, the letter $e$ appears as both $I$ and $X$. If we had used a longer plaintext, $e$ would probably have been encrypted as each of $Z$, $I$, $G$, $X$, $S$, and $V$, corresponding to the shifts 21, 4, 2, 19, 14, 17. But the occurrences of $Z$ in a ciphertext might not come only from $e$. The letter $v$ is also encrypted to $Z$ when its position in the text is such that it is shifted by 4. Similarly, $x$, $g$, $l$, and $i$ can contribute $Z$ to the ciphertext, so the frequency of $Z$ is a combination of that of $e$, $v$, $x$, $g$, $l$, and $i$ from the plaintext. Therefore, it appears to be much more difficult to deduce anything from a frequency count. In fact, the frequency counts are usually smoothed out and are much closer to 1/26 for each letter of ciphertext. At least, they should be much closer than the original distribution for English letters.

Here is a more substantial example. This example is also treated in Example 4 in the Computer Appendices. The ciphertext is the following:

VVHQWVVRHMUSGJGTHKIHTSSEJCHLSFCBGVWCRLRYQTFSVGAHW KCUHWAUGLQHNSLRLJSHBLTSPISPRDXLJSVEEGHLQWKASSKUWE PWQTWVSPGOELKCQYFNSVWLJSNIQKGNRGYBWLWGOVIOKHKAZKQ KXZGYHCECMEIUJOQKWFWVEFQHKIJRCLRLKBIENQFRJLJSDHGR HLSFQTWLAUQRHWDMWLGUSGIKKFLRYVCWVSPGPMLKASSJVOQXE GGVEYGGZMLJCXXLJSVPAIVWIKVRDRYGFRJLJSLVEGGVEYGGEI APUUISFPBTGNWWMUCZRVTWGLRWUGUMNCZVILE

The frequencies are as follows:

Note that there is no letter whose frequency is significantly larger than the others. As discussed previously, this is because $e$, for example, gets spread among several letters during the encryption process.

How do we decrypt the message? There are two steps: finding the key length and finding the key. In the following, we’ll first show how to find the key length and then give one way to find the key. After an explanation of why the method for finding the key works, we give an alternative way to find the key.

One of the more popular cryptosystems is the substitution cipher. It is commonly used in the puzzle section of the weekend newspapers, for example. The principle is simple: Each letter in the alphabet is replaced by another (or possibly the same) letter. More precisely, a permutation of the alphabet is chosen and applied to the plaintext. In the puzzle pages, the spaces between the words are usually preserved, which is a big advantage to the solver, since knowledge of word structure becomes very useful. However, to increase security it is better to omit the spaces.

The shift and affine ciphers are examples of substitution ciphers. The Vigenère cipher (see Section 2.3) is not, since it permutes blocks of letters rather than one letter at a time.

Everyone “knows” that substitution ciphers can be broken by frequency counts. However, the process is more complicated than one might expect.

Consider the following example. Thomas Jefferson has a potentially treasonous message that he wants to send to Ben Franklin. Clearly he does not want the British to read the text if they intercept it, so he encrypts it using a substitution cipher. Fortunately, Ben Franklin knows the permutation being used, so he can simply reverse the permutation to obtain the original message (of course, Franklin was quite clever, so perhaps he could have decrypted it without previously knowing the key).

Now suppose we are working for the Government Code and Cypher School in England back in 1776 and are given the following intercepted message to decrypt.

LWNSOZBNWVWBAYBNVBSQWVWOHWDIZWRBBNPBPOOUWRPAWXAW

PBWZWMYPOBNPBBNWJPAWWRZSLWZQJBNWIAXAWPBSALIBNXWA

BPIRYRPOIWRPQOWAIENBVBNPBPUSREBNWVWPAWOIHWOIQWAB

JPRZBNWFYAVYIBSHNPFFIRWVVBNPBBSVWXYAWBNWVWAIENBV

ESDWARUWRBVPAWIRVBIBYBWZPUSREUWRZWAIDIREBNWIATYV

BFSLWAVHASUBNWXSRVWRBSHBNWESDWARWZBNPBLNWRWDWAPR

JHSAUSHESDWARUWRBQWXSUWVZWVBAYXBIDWSHBNWVWWRZVIB

IVBNWAIENBSHBNWFWSFOWBSPOBWASABSPQSOIVNIBPRZBSIR

VBIBYBWRWLESDWARUWRBOPJIREIBVHSYRZPBISRSRVYXNFAI

RXIFOWVPRZSAEPRIKIREIBVFSLWAVIRVYXNHSAUPVBSVWWUU

SVBOICWOJBSWHHWXBBNWIAVPHWBJPRZNPFFIRWVV

A frequency count yields the following (there are 520 letters in the text):

The approximate frequencies of letters in English were given in Section 2.3. We repeat some of the data here in Table 2.2. This allows us to guess with reasonable confidence that $W$ represents $e$ (though $B$ is another possibility). But what about the other letters? We can guess that $B\text{,}R\text{,}S\text{,}I$, $V\text{,}A\text{,}P\text{,}N$, with maybe an exception or two, are probably the same as $t\text{,}a\text{,}o\text{,}i\text{,}n\text{,}s\text{,}h\text{,}r$ in some order. But a simple frequency count is not enough to decide which is which. What we need to do now is look at digrams, or pairs of letters. We organize our results in Table 2.3 (we only use the most frequent letters here, though it would be better to include all).

Table 2.2 Frequencies of Most Common Letters in English

Table 2.3 Counting Digrams

The entry 1 in the $W$ row and $N$ column means that the combination $WN$ appears 1 time in the text. The entry 14 in the $N$ row and $W$ column means that $NW$ appears 14 times.

We have already decided that $W=e$, but if we had extended the table to include low-frequency letters, we would see that $W$ contacts many of these letters, too, which is another characteristic of $e$. This helps to confirm our guess.

The vowels $a\text{,}i\text{,}o$ tend to avoid each other. If we look at the $R$ row, we see that $R$ does not precede $S\text{,}I\text{,}A\text{,}N$ very often. But a look at the $R$ column shows that $R$ follows $S\text{,}I\text{,}A$ fairly often. So we suspect that $R$ is not one of $a\text{,}i\text{,}o\text{.}$ $V$ and $N$ are out because they would require $a$, $i$, or $o$ to precede $W=e$ quite often, which is unlikely. Continuing, we see that the most likely possibilities for $a\text{,}i\text{,}o$ are $S\text{,}I\text{,}P$ in some order.

The letter $n$ has the property that around 80% of the letters that precede it are vowels. Since we already have identified $W\text{,}S\text{,}I\text{,}P$ as vowels, we see that $R$ and $A$ are the most likely candidates. We’ll have to wait to see which is correct.

The letter $h$ often appears before $e$ and rarely after it. This tells us that $N=h$.

The most common digram is $th$. Therefore, $B=t$.

Among the frequent letters, $r$ and $s$ remain, and they should equal $V$ and one of $A\text{,}R$. Since $r$ pairs more with vowels and $s$ pairs more with consonants, we see that $V$ must be $s$ and $r$ is represented by either $A$ or $R$.

The combination $rn$ should appear more than $nr$, and $AR$ is more frequent than $RA$, so our guess is that $A=r$ and $R=n$.

We can continue the analysis and determine that $S=o$ (note that $to$ is much more common than $ot$), $I=i$, and $P=a$ are the most likely choices. We have therefore determined reasonable guesses for 382 of the 520 characters in the text:

At this point, knowledge of the language, middle-level frequencies ($l\text{,}d\text{,}\dots$), and educated guesses can be used to fill in the remaining letters. For example, in the first line a good guess is that $Y=u$ since then the word $truths$ appears. Of course, there is a lot of guesswork, and various hypotheses need to be tested until one works.

Since the preceding should give the spirit of the method, we skip the remaining details. The decrypted message, with spaces (but not punctuation) added, is as follows (the text is from the middle of the Declaration of Independence):

we hold these truths to be self evident that all men are created equal that they are endowed by their creator with certain unalienable rights that among these are life liberty and the pursuit of happiness that to secure these rights governments are instituted among men deriving their just powers from the consent of the governed that whenever any form of government becomes destructive of these ends it is the right of the people to alter or to abolish it and to institute new government laying its foundation on such principles and organizing its powers in such form as to seem most likely to effect their safety and happiness

Cryptography has appeared in many places in literature, for example, in the works of Edgar Allen Poe (The Gold Bug), William Thackeray (The History of Henry Esmond), Jules Verne (Voyage to the Center of the Earth), and Agatha Christie (The Four Suspects).

Here we give a summary of an enjoyable tale by Arthur Conan Doyle, in which Sherlock Holmes displays his usual cleverness, this time by breaking a cipher system. We cannot do the story justice here, so we urge the reader to read The Adventure of the Dancing Men in its entirety. The following is a cryptic, and cryptographic, summary of the plot.

Mr. Hilton Cubitt, who has recently married the former Elsie Patrick, mails Sherlock Holmes a letter. In it is a piece of paper with dancing stick figures that he found in his garden at Riding Thorpe Manor:

Two weeks later, Cubitt finds another series of figures written in chalk on his toolhouse door:

Two mornings later another sequence appears:

Three days later, another message appears:

Cubitt gives copies of all of these to Holmes, who spends the next two days making many calculations. Suddenly, Holmes jumps from his chair, clearly having made a breakthrough. He quickly sends a long telegram to someone and then waits, telling Watson that they will probably be going to visit Cubitt the next day. But two days pass with no reply to the telegram, and then a letter arrives from Cubitt with yet another message:

Holmes studies it and says they need to travel to Riding Thorpe Manor as soon as possible. A short time later, a reply to Holmes’s telegram arrives, and Holmes indicates that the matter has become even more urgent. When Holmes and Watson arrive at Cubitt’s house the next day, they find the police already there. Cubitt has been shot dead. His wife, Elsie, has also been shot and is in critical condition (although she survives). Holmes asks several questions and then has someone deliver a note to a Mr. Abe Slaney at nearby Elrige’s Farm. Holmes then explains to Watson and the police how he decrypted the messages. First, he guessed that the flags on some of the figures indicated the ends of words. He then noticed that the most common figure was

so it was likely $E$. This gave the fourth message as –E–E–. The possibilities LEVER, NEVER, SEVER came to mind, but since the message was probably a one word reply to a previous message, Holmes guessed it was NEVER. Next, Holmes observed that

had the form E– – –E, which could be ELSIE. The third message was therefore – – – E   ELSIE. Holmes tried several combinations, finally settling on COME ELSIE as the only viable possibility. The first message therefore was – M   –ERE   – – E   SL– NE–. Holmes guessed that the first letter was $A$ and the third letter as $H$, which gave the message as AM HERE A–E SLANE–. It was reasonable to complete this to AM HERE ABE SLANEY. The second message then was A–   ELRI–ES. Of course, Holmes correctly guessed that this must be stating where Slaney was staying. The only letters that seemed reasonable completed the phrase to AT ELRIGES. It was after decrypting these two messages that Holmes sent a telegram to a friend at the New York Police Bureau, who sent back the reply that Abe Slaney was “the most dangerous crook in Chicago.” When the final message arrived, Holmes decrypted it to ELSIE –RE–ARE TO MEET THY GO–. Since he recognized the missing letters as $P\text{,}P\text{,}D\text{,}$ respectively, Holmes became very concerned and that’s why he decided to make the trip to Riding Thorpe Manor.

When Holmes finishes this explanation, the police urge that they go to Elrige’s and arrest Slaney immediately. However, Holmes suggests that is unnecessary and that Slaney will arrive shortly. Sure enough, Slaney soon appears and is handcuffed by the police. While waiting to be taken away, he confesses to the shooting (it was somewhat in self-defense, he claims) and says that the writing was invented by Elsie Patrick’s father for use by his gang, the Joint, in Chicago. Slaney was engaged to be married to Elsie, but she escaped from the world of gangsters and fled to London. Slaney finally traced her location and sent the secret messages. But why did Slaney walk into the trap that Holmes set? Holmes shows the message he wrote:

From the letters already deduced, we see that this says COME HERE AT ONCE. Slaney was sure this message must have been from Elsie since he was certain no one outside of the Joint could write such messages. Therefore, he made the visit that led to his capture.

The Playfair and ADFGX ciphers were used in World War I by the British and the Germans, respectively. By modern standards, they are fairly weak systems, but they took real effort to break at the time.

The Playfair system was invented around 1854 by Sir Charles Wheatstone, who named it after his friend, the Baron Playfair of St. Andrews, who worked to convince the government to use it. In addition to being used in World War I, it was used by the British forces in the Boer War.

The key is a word, for example, playfair. The repeated letters are removed, to obtain playfir, and the remaining letters are used to start a $5\times 5$ matrix. The remaining spaces in the matrix are filled in with the remaining letters in the alphabet, with $i$ and $j$ being treated as one letter:

Suppose the plaintext is meet at the schoolhouse. Remove spaces and divide the text into groups of two letters. If there is a doubled letter appearing as a group, insert an $x$ and regroup. Add an extra $x$ at the end to complete the last group, if necessary. Our plaintext becomes

Now use the matrix to encrypt each two-letter group by the following scheme:

• If the two letters are not in the same row or column, replace each letter by the letter that is in its row and is in the column of the other letter. For example, et becomes $MN$, since $M$ is in the same row as $e$ and the same column as $t$, and $N$ is in the same row as $t$ and the same column as $e$.

• If the two letters are in the same row, replace each letter with the letter immediately to its right, with the matrix wrapping around from the last column to the first. For example, me becomes $EG$.

• If the two letters are in the same column, replace each letter with the letter immediately below it, with the matrix wrapping around from the last row to the first. For example, $ol$ becomes $VR$.

The ciphertext in our example is

To decrypt, reverse the procedure.

The system succumbs to a frequency attack since the frequencies of the various digrams (two-letter combinations) in English have been tabulated. Of course, we only have to look for the most common digrams; they should correspond to the most common digrams in English: $th$, $he$, $an$, $in$, $re$, $es$, $\dots$. Moreover, a slight modification yields results more quickly. For example, both of the digrams $re$ and $er$ are very common. If the pairs $IG$ and $GI$ are common in the ciphertext, then a good guess is that $e$, $i$, $r$, $g$ form the corners of a rectangle in the matrix. Another weakness is that each plaintext letter has only five possible corresponding ciphertext letters. Also, unless the keyword is long, the last few rows of the matrix are predictable. Observations such as these allow the system to be broken with a ciphertext-only attack. For more on its cryptanalysis, see [Gaines].

The ADFGX cipher proceeds as follows. Put the letters of the alphabet into a $5\times 5$ matrix. The letters $i$ and $j$ are treated as one, and the columns of the matrix are labeled with the letters $A\text{,}D\text{,}F\text{,}G\text{,}X$. For example, the matrix could be

Each plaintext letter is replaced by the label of its row and column. For example, $s$ becomes $FA$, and $z$ becomes $DG$. Suppose the plaintext is

The result of this initial step is

So far, this is a disguised substitution cipher. The next step increases the complexity significantly. Choose a keyword, for example, Rhein. Label the columns of a matrix by the letters of the keyword and put the result of the initial step into another matrix:

Now reorder the columns so that the column labels are in alphabetic order:

Finally, the ciphertext is obtained by reading down the columns (omitting the labels) in order:

Decryption is easy, as long as you know the keyword. From the length of the keyword and the length of the ciphertext, the length of each column is determined. The letters are placed into columns, which are reordered to match the keyword. The original matrix is then used to recover the plaintext.

The initial matrix and the keyword were changed frequently, making cryptanalysis more difficult, since there was only a limited amount of ciphertext available for any combination. However, the system was successfully attacked by the French cryptanalyst Georges Painvin and the Bureau du Chiffre, who were able to decrypt a substantial number of messages.

Here is one technique that was used. Suppose two different ciphertexts intercepted at approximately the same time agree for the first several characters. A reasonable guess is that the two plaintexts agree for several words. That means that the top few entries of the columns for one are the same as for the other. Search through the ciphertexts and find other places where they agree. These possibly represent the beginnings of the columns. If this is correct, we know the column lengths. Divide the ciphertexts into columns using these lengths. For the first ciphertext, some columns will have one length and others will be one longer. The longer ones represent columns that should be near the beginning; the other columns should be near the end. Repeat for the second ciphertext. If a column is long for both ciphertexts, it is very near the beginning. If it is long for one ciphertext and not for the other, it goes in the middle. If it is short for both, it is near the end. At this point, try the various orderings of the columns, subject to these restrictions. Each ordering corresponds to a potential substitution cipher. Use frequency analysis to try to solve these. One should yield the plaintext, and the initial encryption matrix.

The letters $ADFGX$ were chosen because their symbols in Morse code ($\cdot -$, $-\cdot \cdot$, $\cdot \cdot -\cdot$, $--\cdot$, $-\cdot \cdot -$) were not easily confused. This was to avoid transmission errors, and represents one of the early attempts to combine error correction with cryptography. Eventually, the $ADFGX$ cipher was replaced by the $ADFGVX$ cipher, which used a $6\times 6$ initial matrix. This allowed all 26 letters plus 10 digits to be used.

For more on the cryptanalysis of the ADFGX cipher, see [Kahn].

Mechanical encryption devices known as rotor machines were developed in the 1920s by several people. The best known was designed by Arthur Scherbius and became the famous Enigma machine used by the Germans in World War II.

It was believed to be very secure and several attempts at breaking the system ended in failure. However, a group of three Polish cryptologists, Marian Rejewski, Henryk Zygalski, and Jerzy Różycki, succeeded in breaking early versions of Enigma during the 1930s. Their techniques were passed to the British in 1939, two months before Germany invaded Poland. The British extended the Polish techniques and successfully decrypted German messages throughout World War II.

The fact that Enigma had been broken remained a secret for almost 30 years after the end of the war, partly because the British had sold captured Enigma machines to former colonies and didn’t want them to know that the system had been broken.

In the following, we give a brief description of Enigma and then describe an attack developed by Rejewski. For more details, see for example [Kozaczuk], which contains appendices by Rejeweski giving details of attacks on Enigma.

We give a basic schematic diagram of the machine in Figure 2.1. For more details, we urge the reader to visit some of the many websites that can be found on the Internet that give pictures of actual Enigma machines and extensive diagrams of the internal workings of these machines. There are also several online Enigma simulators. Try one of them to get a better understanding of how Enigma works.

Figure 2.1 A Schematic Diagram of the Enigma Machine

$L\text{,}M\text{,}N$ are the rotors. On one side of each rotor are 26 fixed electrical contacts, arranged in a circle. On the other side are 26 spring-loaded contacts, again arranged in a circle so as to touch the fixed contacts of the adjacent rotor. Inside each rotor, the fixed contacts are connected to the spring-loaded contacts in a somewhat random manner. These connections are different in each rotor. Each rotor has 26 possible initial settings.

$R$ is the reversing drum. It has 26 spring-loaded contacts, connected in pairs.

$K$ is the keyboard and is the same as a typewriter keyboard.

$S$ is the plugboard. It has approximately six pairs of plugs that can be used to interchange six pairs of letters.

When a key is pressed, the first rotor $N$ turns 1/26 of a turn. Then, starting from the key, electricity passes through $S$, then through the rotors $N\text{,}M\text{,}L$. When it reaches the reversing drum $R$, it is sent back along a different path through $L\text{,}M\text{,}N$, then through $S$. At this point, the electricity lights a bulb corresponding to a letter on the keyboard, which is the letter of the ciphertext.

Since the rotor $N$ rotates before each encryption, this is much more complicated than a substitution cipher. Moreover, the rotors $L$ and $M$ also rotate, but much less often, just like the wheels on a mechanical odometer.

Decryption uses exactly the same method. Suppose a sender and receiver have identical machines, both set to the same initial positions. The sender encrypts the message by typing it on the keyboard and recording the sequence of letters indicated by the lamps. This ciphertext is then sent to the receiver, who types the ciphertext into the machine. The sequence of letters appearing in the lamps is the original message. This can be seen as follows. Lamp “a” and key “a” are attached to a wire coming out of the plugboard. Lamp “h” and key “h” are attached to another wire coming out of the plugboard. If the key “a” is pressed and the lamp “h” lights up, then the electrical path through the machine is also connecting lamp “a” to key “h”. Therefore, if the “h” key were pressed instead, then the “a” key would light.

Similar reasoning shows that no letter is ever encrypted as itself. This might appear to be a good idea, but actually it is a weakness since it allows a cryptanalyst to discard many possibilities at the start. See Chapter 14.

The security of the system rests on the keeping secret the initial settings of the rotors, the setting of the plugs on the plugboard, and the internal wiring of the rotors and reversing drum. The settings of the rotors and the plugboard are changed periodically (for example, daily).

We’ll assume the internal wiring of the rotors is known. This would be the case if a machine were captured, for example. However, there are ways to deduce this information, given enough ciphertext, and this is what was actually done in some cases.

How many combinations of settings are there? There are 26 initial settings for each of the three rotors. This gives ${26}^3=17576$ possibilities. There are six possible orderings of the three rotors. This yields $6\times 17576=105456$ possible ways to initialize the rotors. In later versions of Enigma, there were five rotors available, and each day three were chosen. This made 60 possible orderings of the rotors and therefore 1054560 ways to initialize the rotors.

On the plugboard, there are 100391791500 ways of interchanging six pairs of letters.

In all, there seem to be too many possible initializations of the machine to have any hope of breaking the system. Techniques such as frequency analysis fail since the rotations of the rotors change the substitution for each character of the message.

So, how was Enigma attacked? We don’t give the whole attack here, but rather show how the initial settings of the rotors were determined in the years around 1937. This attack depended on a weakness in the protocol being used at that time, but it gives the general flavor of how the attacks proceeded in other situations.

Each Enigma operator was given a codebook containing the daily settings to be used for the next month. However, if these settings had been used without modification, then each message sent during a given day would have had its first letter encrypted by the same substitution cipher. The rotor would then have turned and the second letter of each text would have corresponded to another substitution cipher, and this substitution would have been the same for all messages for that day. A frequency analysis on the first letter of each intercepted message during a day would probably allow a decryption of the first letter of each text. A second frequency analysis would decrypt the second letters. Similarly, the remaining letters of the ciphertexts (except for the ends of the longest few ciphertexts) could be decrypted.

To avoid this problem, for each message the operator chose a message key consisting of a sequence of three letters, for example, $r\text{,}f\text{,}u$. He then used the daily setting from the codebook to encrypt this message key. But since radio communications were prone to error, he typed in $rfu$ twice, therefore encrypting $rfurfu$ to obtain a string of six letters. The rotors were then set to positions $r$, $f$, and $u$ and the encryption of the actual message began. So the first six letters of the transmitted message were the encrypted message key, and the remainder was the ciphertext. Since each message used a different key, frequency analysis didn’t work.

The receiver simply used the daily settings from the codebook to decrypt the first six letters of the message. He then reset the rotors to the positions indicated by the decrypted message key and proceeded to decrypt the message.

The duplication of the key was a great aid to the cryptanalysts. Suppose that on some day you intercept several messages, and among them are three that have the following initial six letters:

dmqvbn

vonpuy

pucfmq

All of these were encrypted with the same daily settings from the codebook. The first encryption corresponds to a permutation of the 26 letters; let’s call this permutation $A$. Before the second letter is encrypted, a rotor turns, so the second letter uses another permutation; call it $B$. Similarly, there are permutations $C$, $D$, $E$, $F$ for the remaining four letters. The strategy is to look at the products $AD$, $BE$, and $CF$.

We need a few conventions and facts about permutations. When we write $AD$ for two permutations $A$ and $D$, we mean that we apply the permutation $A$ then $D$ (some books use the reverse ordering). The permutation that maps $a$ to $b$, $b$ to $c$, and $c$ to $a$ will be denoted as the 3-cycle $(abc)$. A similar notation will be used for cycles of other lengths. For example, $(ab)$ is the permutation that switches $a$ and $b$. A permutation can be written as a product of cycles. For example, the permutation

is the permutation that maps $d$ to $v$, $v$ to $p$, $t$ to $e$, $r$ to $w$, etc., and fixes $a$ and $s$. If the cycles are disjoint (meaning that no two cycles have letters in common), then this decomposition into cycles is unique.

Let’s look back at the intercepted texts. We don’t know the letters of any of the three message keys, but let’s call the first message key $xyz$. Therefore, $xyzxyz$ encrypts to $dmqvbn$. We know that permutation $A$ sends $x$ to $d$. Also, the fourth permutation $D$ sends $x$ to $v$. But we know more. Because of the internal wiring of the machine, $A$ actually interchanges $x$ and $d$ and $D$ interchanges $x$ and $v$. Therefore, the product of the permutations, $AD$, sends $d$ to $v$ (namely, $A$ sends $d$ to $x$ and then $D$ sends $x$ to $v$). The unknown $x$ has been eliminated. Similarly, the second intercepted text tells us that $AD$ sends $v$ to $p$, and the third tells us that $AD$ sends $p$ to $f$. We have therefore determined that

In the same way, the second and fifth letters of the three messages tell us that

and the third and sixth letters tell us that

With enough data, we can deduce the decompositions of $AD$, $BE$, and $CF$ into products of cycles. For example, we might have

This information depends only on the daily settings of the plugboard and the rotors, not on the message key. Therefore, it relates to every machine used on a given day.

Let’s look at the effect of the plugboard. It introduces a permutation $S$ at the beginning of the process and then adds the inverse permutation $S^{-1}$ at the end. We need another fact about permutations: Suppose we take a permutation $P$ and another permutation of the form $SP{S}^{-1}$ for some permutation $S$ (where $S^{-1}$ denotes the inverse permutation of $S$; in our case, $S=S^{-1}$) and decompose each into cycles. They will usually not have the same cycles, but the lengths of the cycles in the decompositions will be the same. For example, $AD$ has cycles of length 10, 10, 2, 2, 1, 1. If we decompose $SAD{S}^{-1}$ into cycles for any permutation $S$, we will again get cycles of lengths 10, 10, 2, 2, 1, 1. Therefore, if the plugboard settings are changed, but the initial positions of the rotors remain the same, then the cycle lengths remain unchanged.

You might have noticed that in the decomposition of $AD$, $BE$, and $CF$ into cycles, each cycle length appears an even number of times. This is a general phenomenon. For an explanation, see Appendix E of the aforementioned book by Kozaczuk.

Rejewski and his colleagues compiled a catalog of all 105456 initial settings of the rotors along with the set of cycle lengths for the corresponding three permutations $AD$, $BE$, $CF$. In this way, they could take the ciphertexts for a given day, deduce the cycle lengths, and find the small number of corresponding initial settings for the rotors. Each of these substitutions could be tried individually. The effect of the plugboard (when the correct setting was used) was then merely a substitution cipher, which was easily broken. This method worked until September 1938, when a modified method of transmitting message keys was adopted. Modifications of the above technique were again used to decrypt the messages. The process was also mechanized, using machines called “bombes” to find daily keys, each in around two hours.

These techniques were extended by the British at Bletchley Park during World War II and included building more sophisticated “bombes.” These machines, designed by Alan Turing, are often considered to have been the first electronic computers.